/*
 *https://leetcode.cn/problems/minimum-insertion-steps-to-make-a-string-palindrome/description/
 *1312. 让字符串成为回文串的最少插入次数
 *difficult 吴朝泽 2024.10.15
 *区间DP
*/

class Solution {
public:
    int minInsertions(string s) {
        int n = s.size(); 
        int f[n][n]; // 存储子问题的结果
        memset(f, 0, sizeof(f)); 

        // 从倒数第二个字符开始，向前遍历
        for (int i = n - 2; i >= 0; --i) 
        {
            // 内层循环，从 i+1 开始到 n-1
            for (int j = i + 1; j < n; ++j) 
            {
                // 如果 s[i] 和 s[j] 相等
                if (s[i] == s[j]) 
                {
                    // 那么不需要插入字符，继承子问题的解
                    f[i][j] = f[i + 1][j - 1];
                } else {
                    // 否则，需要在两种情况中选择插入字符的最小次数
                    // 一种是忽略 s[i]，即计算 f[i + 1][j]
                    // 另一种是忽略 s[j]，即计算 f[i][j - 1]
                    // 加 1 是因为我们需要插入一个字符
                    f[i][j] = min(f[i + 1][j], f[i][j - 1]) + 1;
                }
            }
        }
        return f[0][n - 1];
    }
};
